package LeetCode.leetcode707;

/**
 * 超时！！
 */

class Review1 {
    private int size;
    private Node virtualNode;

    public Review1() {
        size = 0;
        virtualNode = new Node();
        virtualNode.next = null;
    }

    public int get(int index) {
        if (index < 0 || index > size - 1) return -1;
        Node p = virtualNode;
        for (int i = 0; i <= index; i++) {
            p = p.next;
        }
        return p.val;
    }

    public void addAtHead(int val) {
        Node newNode = new Node();
        newNode.val = val;
        newNode.next = virtualNode.next;
        virtualNode.next = newNode;
        size++;
    }

    public void addAtTail(int val) {
        Node p = virtualNode;
        while (p.next != null){
            p = p.next;
        }
        Node newNode = new Node();
        newNode.val = val;
        p.next = virtualNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index + 1 > size) return;
        else if (index <= 0){
            Node newNode = new Node();
            newNode.val = val;
            newNode.next = virtualNode.next;
            virtualNode.next = newNode;
            size++;
        }else if (index + 1 == size){
            Node p = virtualNode;
            while (p.next != null){
                p = p.next;
            }
            Node newNode = new Node();
            newNode.val = val;
            p.next = virtualNode;
            size++;
        }else {
            Node p = virtualNode;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            Node newNode = new Node();
            newNode.val = val;
            newNode.next = p.next;
            p.next = newNode;
            size++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index + 1 > size) return;
        Node p = virtualNode;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        p.next = p.next.next;
    }
    public static class Node {
        int val;
        Node next;
    }
}
